#include <stdio.h>
#include <string.h>

// dp: 最优子结构性质，问题的最优解包含了子问题的最优解
// 用c99标准或cpp
// n: 问题规模
// p[]: p[n+1]就可以存放所有矩阵的行列
// m[i][j]: 存储最优子结构，计算A[i, j]（i～j个矩阵连乘）最少的连乘次数
// 当i=j时表示只有一个矩阵，m[i][j]=0（所以构造的表左上至右下的对角线都为0）
// 当i<j时矩阵连乘才能进行，m[i][j]=min{m[i, k] + m[k+1, j] + Pi-1PkPi}
// 按对角线填表: 连乘矩阵数在一条对角线上一样多，[1,2] [2,3] [3,4] [4,5]...
// 根据前面填完的对角线相邻的不同两行加上p[i-1]p[k]p[j],再将两值比较得到拐角处的值
// s[i][j]: 记录下A[i, j]最优解的位置k

void matrixChain(int n, int p[], int m[][100], int s[][100]) {
	for (int i = 1; i < n; ++i) {
		m[i][i] = 0;  // 对角线为0,不用0行0列
	}
	for (int r = 2; r <= n; ++r) {  // 第r条，右上部分剩余的n-1条对角线
		for (int i = 1; i <= n-r+1; ++i) {  // 第i行，准备按对角线从左上至右下填表
			int j = i+r-1;  // 对角线第j列
			m[i][j] = m[i+1][j] + p[i-1]*p[i]*p[j];  // 初始化此时i处取得最优解
			s[i][j] = i;
			for (int k = i+1; k < j; ++k) {  // 如果有更小的则替换
				// k=i+1可以知道第2条对角线并不参与比较
				int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
				if (t < m[i][j]) {
					m[i][j] = t;
					s[i][j] = k;
				}
			}
		}
		
	}
}

void print_optimal_parents(int s[100][100], int i, int j) {
	if (i == j)
		printf("A%d", i);
	else {
		printf("(");
		print_optimal_parents(s, i, s[i][j]);
		print_optimal_parents(s, s[i][j]+1, j);
		printf(")");
	}
}

int main(int argc, const char** argv) {
	int p[1000];
	int m[100][100];
	int s[100][100];
	memset(p, 0, sizeof(p));
	memset(m, 0, sizeof(m));
	memset(s, 0, sizeof(s));
	
	printf("Enter Number of Matrix:\n");
	int n;
	scanf("%d", &n);

	printf("Enter Every Matrix Number of Rows and the Number of Columns of Last Matrix:\n");
	for (int i = 0; i <= n; ++i) {  // n+1个
		scanf("%d", p+i);
	}

	matrixChain(n, p, m, s);
	printf("The Minimum Number of Mul: %d\n", m[1][n]);	

	printf("Result:\n");
	print_optimal_parents(s, 1, n);
	return 0;

}
